import java.io.*;
import java.util.StringTokenizer;

public final class Ejercicio2 implements Ejercicio
{
	private int _elementos;
	private int _valor;
	
	public void execute(String strFileIn, String strFileOut)
	{
		//archivo entrada
		RandomAccessFile fin;
		//para borrar la salida anterior
		File foutDelete;
		//archivo salida
		RandomAccessFile fout;
		
		try
		{
			int i;
			
			//abro el archivo
			fin = new RandomAccessFile(strFileIn,"r");
			
			//buffer de entrada y salida
			String strOutBuffer = "", strInBuffer = fin.readLine();
			//cantidad de elementos y peso maximo
			int n, p;
			//para recorrer la linea del arreglo
			StringTokenizer stk; String strToken;
			//arreglo de elementos
			ValorPeso a[];
			//valor y peso del elemento
			int ve, pe;
			//resultado de cada problema
			Resultado res;
			
			//levanto cada caso
			while( strInBuffer != null && !strInBuffer.equals("Fin") )
			{
				n = 0; p = 0;
				
				//si es un nuevo caso
				if( strInBuffer.equals("Caso") )
				{
					//siguiente linea
					strInBuffer = fin.readLine();
					//hago un arreglo
					stk = new StringTokenizer( strInBuffer, " " );
					
					//levanto la cantidad de elementos
					while( stk.hasMoreTokens() && n == 0 )
					{
						//siguiente elemento
						strToken = stk.nextToken();
						
						//si no es un espacio
						if( strToken != "" && strToken != null )
							n = new Integer( strToken ).intValue();
					}
					
					//levanto el peso maximo
					while( stk.hasMoreTokens() && p == 0 )
					{
						//siguiente elemento
						strToken = stk.nextToken();
						
						//si no es un espacio
						if( strToken != "" && strToken != null )
							p = new Integer( strToken ).intValue();
					}
					
					//creo el arreglo de elementos
					a = new ValorPeso[n];
					
					//levanto cada elemento
					for(i = 0; i < n; i++)
					{
						ve = 0; pe = 0;
						
						//siguiente linea
						strInBuffer = fin.readLine();
						//hago un arreglo
						stk = new StringTokenizer( strInBuffer, " " );
						
						//levanto el valor del elemento
						while( stk.hasMoreTokens() && ve == 0 )
						{
							//siguiente elemento
							strToken = stk.nextToken();
							
							//si no es un espacio
							if( strToken != "" && strToken != null )
								ve = new Integer( strToken ).intValue();
						}
						
						//levanto el peso del elemento
						while( stk.hasMoreTokens() && pe == 0 )
						{
							//siguiente elemento
							strToken = stk.nextToken();
							
							//si no es un espacio
							if( strToken != "" && strToken != null )
								pe = new Integer( strToken ).intValue();
						}
						
						//elemento
						a[i] = new ValorPeso(ve,pe,i);
					}
					
					//levanto el resultado del caso
					res = cargarCamion(a,n,p);
					
					//guardo el buffer de salida
					strOutBuffer+= res.valor + " " + res.elementos;
					
					for(i = 0; i < res.elementos; i++)
						strOutBuffer+= " " + res.indices[i];
				}
				
				strOutBuffer+= "\n";
				
				//siguiente linea
				strInBuffer = fin.readLine();
			}
			
			//cierro el archivo
			fin.close();
			
			//borro el archivo de salida anterior
			foutDelete = new File(strFileOut);
			foutDelete.delete();
			
			//abro el archivo de salida
			fout = new RandomAccessFile(strFileOut,"rw");
			
			//paso el buffer de salida al archivo
			fout.writeBytes(strOutBuffer);
			
			//cierro el archivo de salida
			fout.close();
		}
		catch (IOException e)
		{
			//TODO: error abriendo archivo
		}
	}
	
	private Resultado cargarCamion(ValorPeso a[], int n, int p)
	{
		//solucion parcial y optima
		boolean s[] = new boolean[n], so[] = new boolean[n];
		
		int i, j = 0;
		
		//inicializo ambas con todos los elementos sin elejir
		for( i = 0; i < n; i++ )
			s[i] = so[i] = false;
		
		//valor obtenido
		this._valor = 0;
		//cantidad de elementos usados
		this._elementos = 0;
		
		//ordeno el arreglo
		if( n > 0 )
			pesoQuicksort(a, 0, n-1);
		
		//calculo la solucion optima
		_cargarCamion(a, s, so, n, p, 0);
		
		//levanto los indices usados
		int indices[] = new int[this._elementos];
		
		for( i = 0; i < n; i++ )
		{
			//si la solucion optima tiene el elemento agrego el indice original del elemento
			//le sumo uno pq la solucion requiere indices de 1..n
			if( so[i] )
				indices[j++] = a[i].indice+1;
		}
		
		//reacomodo los indices originales para devolverlos
		if( this._elementos > 0 )
			quicksort(indices, 0, this._elementos-1);
		
		return new Resultado(this._valor, this._elementos, indices);
	}
	
	private void _cargarCamion
	(
			ValorPeso a[],
			boolean s[],
			boolean so[],
			int n,
			int p,
			int k
	){
		if( k < n )
		{
			int v, vo = calcularValor(a,so,n);
			
			_cargarCamion(a,s,so,n,p,k+1);
			s[k] = true;
			
			if( noPasaPeso(a,s,n,p) && alcanzaValorOptimo(a,s,n,vo,k) )
			{
				v = calcularValor(a,s,n);
				
				if( v > vo )
				{
					System.arraycopy(s, 0, so, 0, n);
					this._valor = v;
				}
				else
				{
					this._valor = vo;
				}
				
				this._elementos++;
				
				_cargarCamion(a,s,so,n,p,k+1);
			}
		}
	}
	
	private boolean noPasaPeso
	(
			ValorPeso a[],
			boolean s[],
			int n,
			int p
	){
		int peso = 0;
		
		for( int i = 0; i < n; i++ )
		{
			if( s[i] )
				peso+= a[i].peso;
		}
		
		return peso <= p;
	}
	
	private boolean alcanzaValorOptimo
	(
			ValorPeso a[],
			boolean s[],
			int n,
			int vo,
			int k
	){
		int v = 0;
		
		for( int i = 0; i < n; i++ )
		{
			if( s[i] || i >= k )
				v+= a[i].valor;
		}
		
		return v > vo;
	}
	
	private int calcularValor
	(
			ValorPeso a[],
			boolean s[],
			int n
	){
		int valor = 0;
		
		for( int i = 0; i < n; i++ )
		{
			if( s[i] )
				valor+= a[i].valor;
		}
		
		return valor;
	}
	
	private void pesoQuicksort (ValorPeso[] a, int ini, int end)
	{
	    int i=ini, j=end;
	    int x=a[(ini+end)/2].peso;
	    ValorPeso h;

	    do
	    {    
	        while (a[i].peso>x) i++; 
	        while (a[j].peso<x) j--;
	        if (i<=j)
	        {
	            h=a[i]; a[i]=a[j]; a[j]=h;
	            i++; j--;
	        }
	    } while (i<=j);

	    if (ini<j) pesoQuicksort(a, ini, j);
	    if (i<end) pesoQuicksort(a, i, end);
	}
	
	private void quicksort (int[] a, int ini, int end)
	{
	    int i=ini, j=end, h;
	    int x=a[(int)( (ini+end)/2 )];

	    do
	    {    
	        while (a[i]<x) i++; 
	        while (a[j]>x) j--;
	        if (i<=j)
	        {
	            h=a[i]; a[i]=a[j]; a[j]=h;
	            i++; j--;
	        }
	    } while (i<=j);

	    if (ini<j) quicksort(a, ini, j);
	    if (i<end) quicksort(a, i, end);
	}
	
	private class Resultado
	{
		public int valor;
		public int elementos;
		public int indices[];
		
		public Resultado(int v, int e, int i[])
		{
			this.valor = v;
			this.elementos = e;
			this.indices = i;
		}
	}
	
	private class ValorPeso
	{
		public int valor;
		public int peso;
		public int indice;
		
		public ValorPeso(int v, int p, int i)
		{
			this.valor = v;
			this.peso = p;
			this.indice = i;
		}
	}
}
